﻿/*839. 模拟堆

维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。

输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。

数据范围
1≤N≤105,−109≤x≤109

输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
*/

#include<iostream>
#include<algorithm>
#include<cstring>//strcmp()
using namespace std;
const int N = 100010;
int h[N], hp[N], ph[N], sz;//hp,ph记录映射关系
//ph[i]:第i个插入的数

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}
void down(int u)
{
    int t = u;
    if (u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);//(h[u],h[t]);
        down(t);
    }
}
void up(int u)
{
    while (u / 2 && h[u / 2] > h[u]) //u/2:父节点
    {
        heap_swap(u / 2, u);
        u /= 2;
    }
}
int main()
{
    int n, x, k;
    cin >> n;
    int m = 0;//m用来记录插入的数的个数
    //注意m的意义与sz是不同的 sz是记录堆中当前数据的多少
    //m是第几个插入的数，，，hp中应该存的值？
    char op[3];
    //sz=n;
    while (n--)
    {
        cin >> op;
        if (!strcmp(op, "I")) //strnmp错，strncmp
            //strmp(str1,str2)若str1==str2，则返回零；
        {
            cin >> x;
            sz++;
            /*这个sz为什么不需要赋值==n
 因为n是操作次数，而不是元素个数,那就说明size一开始大小为0，所有的数据是通过"I(serte)"插入到heap内的*/

            m++;
            ph[m] = sz; 
            hp[sz] = m; //互相映射
            h[sz] = x;
            /*上面这三个是没有顺序的o*/
            up(sz); //这个老是忘记
        }
        else if (!strcmp(op, "PM"))   cout << h[1] << endl;
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, sz);
            sz--;
            down(1);
        }
        else if (!strcmp(op, "D"))//删除第k个插入的数
        {
            cin >> k;
            k = ph[k];
            heap_swap(k, sz);
            sz--;
            down(k), up(k);
        }
        else//修改第k个插入的数
        {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
        /*这样也可以：
        if(op[0]=='I')//I x，插入一个数 x
        else if(op[0]=='P')//PM，输出当前集合中的最小值
        else if(op[0]=='D' && op[1]=='M')//DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
        else if(op[0]=='D')//D k，删除第 k 个插入的数
        else if(op[0]=='C')//C k x，修改第 k 个插入的数，将其变为 x
  */
    }
    return 0;
}

/*
什么时候需要p[i]=i这样的赋值但不cin操作？？*/

/*总结：
1.为什么需要hp[],ph[]这样的映射关系？
ph[i]:第i次插入操作，用ph[]来映射插入次数和下标关系不就可以了，为什么还需要hp[]?
 *之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持 原有的 插入顺序
    从而我们需要对应到原先第K个堆中元素，如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换
    h,hp,ph之间两两存在映射关系 所以交换顺序的不同 对结果并不会产生影响

    *ph数组主要用于帮助从idx映射到下标k，
    *在swap操作中我们输入是堆数组的下标，无法知道每个堆数组的k下标对应idx（第idx个插入），所以需要hp数组方便查找idx。
2.up(sz); //这个老是忘记
3.注意if (!strcmp(op, "I")) ，是"!"这个老是忘记
4.(u * 2 <= sz && ..)这个条件可不是 u*2 && .
*/